// https://www.lintcode.com/problem/longest-consecutive-sequence/my-submissions

class Solution {
public:
    /**
     * @param num: A list of integers
     * @return: An integer
     */
    // 法一：遍历
    // int longestConsecutive(vector<int> &num) {
    //     sort(num.begin(), num.end());
    //     int maxLen = 1;
    //     int tmpLen = 1;
    //     for (int i = 1; i < num.size(); ++i)
    //     {
    //         if (num[i] == num[i - 1] + 1) tmpLen++; //注意判断后一个不等于前一个
    //         else if (num[i] != num[i - 1])
    //         { 
    //             tmpLen = 1;
    //         }
    //         maxLen = max(maxLen, tmpLen); //注意要放到外面
    //     }
    //     return maxLen;
    // }
    
    
    // 法二&法三：
    // 考点：
    // • 是否可以跳出排序后扫描的思维定式，以每个元素作为突破点
    
    // • 一种简单的方法是对每个数字，向左向右搜一下，看最长能有多长
    // • 还有一个发现就是，如果4 向左向右搜到了1 2 3 那么1 2 3这三个数字
    // 就不用向左向右搜了（发现冗余）。
    
    // • 时间复杂度怎么算？
    // – 每个元素只会被访问一遍，所以时间复杂度是O(n)
    
    // ◆ 小技巧总结：
    // • Hash可以在O(1)的时间内确定一个元素是否存在，利用这个可以降低
    // 时间复杂度
    // • 计算时间复杂度的方法，“每个元素只会被访问一遍”这句话所代表的
    // 方法很常用
    
    // int longestConsecutive(vector<int> &num) {
    //     map<int, int> record;
    //     int result = 0;
    //     for (int i = 0; i < num.size(); ++i)
    //     {
    //         record[num[i]]++;;
    //     }
    //     for (int i = 0; i < num.size(); ++i)
    //     {
    //         int r = num[i];
    //         int l = num[i] - 1;
    //         while (record.find(r) != record.end() && record[r]) 
    //         {
    //             record[r++]--;
    //         }
    //         while (record.find(l) != record.end() && record[l])
    //         {
    //             record[l--]--;
    //         }
    //         result = max(r - l - 1, result);
    //     }
    //     return result;
    // }
    
    int longestConsecutive(vector<int> &num) {
     // TLE，注意防止重复判断
        set<int> s(num.begin(), num.end());
        int maxLen = 1;
        for (int i = 0; i < num.size(); ++i)
        {
            s.erase(num[i]);
            int r = num[i];
            int l = num[i];
            while (s.find(++r) != s.end()) s.erase(r);
            while (s.find(--l) != s.end()) s.erase(l);
            maxLen = max(maxLen, r - l - 1);
        }
        return maxLen;
        
    }
};